package cn.xmoit.other;

/**
 * @author fangyy
 */
public class ArrayQueue {

	/**
	 * 存储数据的数组
	 */
	private final String[] items;

	/**
	 * 记录数组容量
	 */
	private final int n;

	/**
	 * head记录队头索引
	 */
	private int head = 0;

	/**
	 * tail记录队尾索引
	 */
	private int tail = 0;

	/**
	 * 申请一个指定容量的队列
	 * @param capacity 容量
	 */
	public ArrayQueue(int capacity) {
		items = new String[capacity];
		n = capacity;
	}

	/**
	 * 入队操作，将数据放入队尾
	 * @param item 数据
	 * @return true or false
	 */
	public boolean enqueue(String item) {
		// tail == n表示队列末尾没有空间了
		if (tail == n) {
			// tail ==n && head==0，表示整个队列都占满了
			if (head == 0) {
				return false;
			}
			// 数据搬移
			for (int i = head; i < tail; ++i) {
				items[i - head] = items[i];
			}
			// 搬移完之后重新更新head和tail
			tail -= head;
			head = 0;
		}

		items[tail] = item;
		++tail;
		return true;
	}

	/**
	 * 出队操作
	 * @return 元素内容
	 */
	public String dequeue() {
		// 如果head == tail 表示队列为空
		if (head == tail) {
			return null;
		}
		String res = items[head];
		++head;
		return res;
	}

}